#include <iostream>
using namespace std;

//第N个泰波那契数
//https://leetcode.cn/problems/n-th-tribonacci-number/
//class Solution {
//public:
//    int tribonacci(int n) { //数组填表
//        if (n == 0) return 0;
//        if (n == 1 || n == 2) return 1;
//        vector<int> v(n + 1); //开辟n+1个空间存储
//        v[0] = 0;
//        v[1] = v[2] = 1;
//        for (int i = 3; i <= n; ++i)
//        {
//            v[i] = v[i - 1] + v[i - 2] + v[i - 3];
//        }
//        return v[n];
//    }
//};
//优化
//class Solution {
//public:
//    int tribonacci(int n) { //滚动数组
//        if (n == 0) return 0;
//        if (n == 1 || n == 2) return 1;
//        int a = 0, b = 1, c = 1;
//        for (int i = 3; i <= n; ++i)
//        {
//            int tmp = a + b + c;
//            a = b;
//            b = c;
//            c = tmp;
//        }
//        return c;
//    }
//};


// 三步问题
// https://leetcode.cn/problems/three-steps-problem-lcci/
//class Solution {
//public:
//    int waysToStep(int n) {
//        //1 2 4 7 13 dp[i] = dp[i-1]+dp[i-2]+dp[i-3]
//        int arr[3] = { 1,2,4 };
//        if (n < 4) return arr[n - 1];
//        const int mod = 1e9 + 7;
//        for (int i = 4; i <= n; ++i) //滚动数组
//        {
//            int tmp = ((arr[0] + arr[1]) % mod + arr[2]) % mod;
//            arr[0] = arr[1];
//            arr[1] = arr[2];
//            arr[2] = tmp;
//        }
//        return arr[2];
//    }
//};


//使用最小花费爬楼梯
//https://leetcode.cn/problems/min-cost-climbing-stairs/
//class Solution {
//public:
//    int minCostClimbingStairs(vector<int>& cost) {
//        int n = cost.size();
//        vector<int> v(n + 1);
//        for (int i = 2; i <= n; ++i)
//        {
//            v[i] = min(v[i - 1] + cost[i - 1], v[i - 2] + cost[i - 2]);
//        }
//        return v[n];
//    }
//};
//反向遍历
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n);
        dp[n-1] = cost[n-1];
        dp[n-2] = cost[n-2];
        if(n>2)
        {
            for(int i = n-3;i>=0;--i)
            {
                dp[i] = cost[i] + min(dp[i+1],dp[i+2]); //当前位置的金额是当前这一步需要消耗的钱加上上一步需要的钱
            }
        }
        return min(dp[0],dp[1]);
    }
};